package algo.graph;

import ds.adt.Graph;

/**
 * Implements Depth first search algorithm.
 *
 * @author shankar
 *
 */
public class DepthFirstSearch {

	private boolean[] marked;
	private int count;

	public DepthFirstSearch(Graph g, int s) {
		this.marked = new boolean[g.V()];
		this.count = 0;

		dfs(g, s);
	}

	/**
	 * Recursively visits the vertex v and its adjacent vertices which are not
	 * visited.
	 *
	 * @param g
	 * @param v
	 */
	private void dfs(Graph g, int v) {
		marked[v] = true;
		++count;

		for (int w : g.adj(v)) {
			if (!marked[w]) {
				dfs(g, w);
			}
		}
	}

	public boolean marked(int v) {
		return marked[v];
	}

	public int count() {
		return count;
	}

	public static void main(String[] args) {

		Graph g = new Graph(5);
		g.addEdge(0, 1);
		g.addEdge(1, 2);
		g.addEdge(0, 3);
		g.addEdge(0, 4);

		System.out.println("Graph Adjaceny List =" + g.toString());

		DepthFirstSearch dfs = new DepthFirstSearch(g, 0);
		System.out.print("DFS PATH : ");
		for (int i = 0; i < g.V(); i++) {
			if (dfs.marked(i)) {
				System.out.print(i);
			}
		}
	}
}
